/**
 * 题目：
 * 合并二维有序数组成一维有序数组，归并排序的思路
 */

export function merge(arr:Array<Array<number>>):Array<any> {
  const middle = arr.length>>1;
  if(arr.length<2){
    return arr[0];
  }
  const left = arr.slice(0, middle);
  const right = arr.slice(middle);
  return sort(merge(left), merge(right));
}

function sort(left:Array<number>, right:Array<number>): Array<number>{
  const result:Array<number> = [];
  while(left.length && right.length) {
    if (left[0] >= right[0]) {
      result.push((right.shift() as number));
    }else{
      result.push((left.shift() as number));
    }
  }

  while (left.length) { 
    result.push((left.shift() as number));
  }
  while (right.length) {
    result.push((right.shift() as number));
  }
  return result;
}


